
\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{clrscode}
\usepackage{sectsty} % Allows customizing section commands
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usetikzlibrary{graphs}
\usetikzlibrary{shapes.arrows}
\allsectionsfont{\indent\normalfont\scshape} % Make all sections centered, the default font and small caps
\usepackage{indentfirst}
\setlength{\parindent}{2em}
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage[linesnumbered,boxed,lined,ruled,vlined]{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{graphicx}
\usepackage{float}
%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{中国科学院大学}\ \textsc{计算机与控制学院} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 算法设计与分析第二次作业 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title
Notice:\\
\begin{enumerate}
\item Please submit your answer in hard copy AND submit a digital version to UCAS website http://sep.ucas.ac.cn.
\item Hard copy should be submitted before 9  am. September 30 and digital version should be submitted before 12 pm. September 30.
\item You can choose \textbf{three} from problems 1-7, and choose \textbf{two} from problems 8-11.
\item For problems 1-7, you should do at least the following things:
\begin{enumerate}
 \item Describe your algorithm in natural language \textbf{AND} pseudo-code;
 \item Draw a ``subproblem reduction graph", where nodes represent subproblems, and edges describe the ``reduction relationship" between them for every problem you choose in problems 1-7;
 \item Prove the correctness of your algorithm;
 \item Analyse the complexity of your algorithm.
\end{enumerate}
\item For problems 8-11, you should implement your algorithm in C/C++/Java/Python with good comments.
\end{enumerate}
%----------------------------------------------------------------------------------------
%	PROBLEM 1
%----------------------------------------------------------------------------------------
\newpage
\section{answer to 1th}
given a set of distinct positive integers, find the largest subset such that every pair $(S_i,S_j)$ of element in this subset satisfies: $S_i\% S_j=0$ or $S_j \% S_i=0$.\\
\textbf{问题分析：}\\
\textbf{INPUT:}a set of distinct positive integers $G$.\\
\textbf{OUTPUT:}$S:$ a subset of $G$,satifies $S_i\%S_j=0\ or\ S_j\%S_i=0\ when\ S_i,S_j\in S$\\
该问题要输入是一个集合，输出是输入集合的子集，要求里面的数相互之间能够被整除，且是这样的集合中元素最多的一个。\\
\textbf{method 1: 暴力枚举法}\\
假如集合$G$中有$n$个元素，则一共有$2^n$个子集，我们只需按照子集中元素数目的大小，从大到小一次判断是否满足要求，第一个满足要求的子集即是我们的一个满足要求的解。当然，时间复杂度是$O(2^n)$.\\
\textbf{method 2: DP算法尝试1}\\
将问题的求解过程分解成多步决策的过程。为了计算方便，我们输入改成一个序列（而不是集合）。第$i$步的决策决定是否选择$G(i)$。
我们使用$OPT(G,k)$表示序列$G$中前$k$个元素的最优解，假设我们已经得到了最优解$OPT(G,n)$，那么我们考虑最后一步决策：最优解中是否选择$G(n)$，合理的想法是，假如$G(n)$可以被$OPT(G,n-1)$中的最大元素整除，
则$OPT(G,n)=OPT(G,n-1)+1$，否则$OPT(G,n)=OPT(G,n-1)$。但是很遗憾的是，这个递推过程是错误的，例如$G={1,2,3,9}$,$OPT(G,3)={1,2}$,然而$OPT(G,4)={1,3,9}$,其中9并不能被2整除，所以，此路不通。\\
\textbf{method 3: DP算法尝试2}\\
由上一步的分析可知，$OPT(G,n)$与$OPT(G,n-1)$不存在必然的联系，所以我们不能将多步的决策分解为是否选择第$k$个元素。我们可以讲这个复杂的问题分解为多个简单的问题，定义$OPT'(G,k)$为在序列$G$的前$k$
个元素上最大整除集合，同时该集合包含$G(k)$，那么$OPT(G,n)=\max_{OPT'(G,k)}(|OPT'(G,k)|),k=1,2,...n.$对于$OPT'(G,k)$我们可以采用遍历的方法来解决。同时，一个数的约数一定是比他小的数，
所以可以通过排序来简化遍历。同时，$OPT'(G,m)=OPT'(G,k)$,$G$为已排序的序列，$k$为$G$中$m$的约数中最大的数。对于每一个序列，我们使用回溯法来恢复该序列。
\subsection{Optimal sub-struction}\\
$OPT(G,n)=\max_{OPT'(G,k)}(|OPT'(G,k)|),k=1,2,...n$\\
$OPT'(G,m)=OPT'(G,k),k=\max(\{ u|G(m)\%G(u)=0 \})$
\subsection{pseudo-code}\\
\begin{algorithm}
  \caption{Largest-Divisible-Subset}
      \KwData{G: a list}
      \KwResult{T: a subset of G}
      \Begin{
        \tcp{init}
        $G \leftarrow \text{sort in ascending order}$\\
        $subsetSize_{max} \leftarrow 1$\\
        $subsetIndex_{max} \leftarrow 0$\\
        $len \leftarrow G.length$\\
        \tcp{for back-tracking}
        $record[len]={1:1:len}$\\
        $opt'[len]={1}$\\
        $result$ is a stack for the solution.\\
        \tcp{calculate all opt'}
          \For{$i=2:1:len$}
          {
              \For{$j=1:1:i$}
              {
                  \If{$G[i]\%G[j]==0$}
                  {
                      $record[i]=j;$\\
                      $opt'[i]=opt'[j]+1;$\\
                      \If{$opt'[i]>subsetSize_{max}$}
                      {
                          $subsetSize_{max}=opt'[i];$\\
                          $subsetIndex_{max}=i;$\\
                      }
                  }
              }
          }
          \tcp{back-tracking}
          $k=subsetIndex_{max};$\\
          \While{$record[k] \ne k$}
          {
              $result.pushback(G[k]);$\\
              $k=record[k];$\\
          }
          $result.pushback(G[k]);$\\
          \Return{$result$}
      }
\end{algorithm}
\subsection{Correction}
\subsection{Time complexity}
算法中有两层循环，可知其时间复杂度为$T(n)=O(n^2)$.\\

\newpage
\section{Money Robbing}
A robber is planning to rob houses along a street. each hous has a certain amount of money stashed, the only constraint stopping
you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
\begin{enumerate}
\item Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight alering the ppolice.
\item What if all houses are arranged in a circle.
\end{enumerate}
\subsection{all houses are not in a circle}
\textbf{问题分析：}\\
\textbf{Input:}\\
L: a list about the amount of money for each houses, it is sequential.\\
\textbf{Output:}\\
T: a list that should be broken for maximum money.\\
这是一个多步决策的过程，显然应该使用动态规划的思想求解。
\subsubsection{optimal substructure}
\begin{itemize}
\item Suppose we have get the optimal solution.
\item Consider the first decision, i.e. whether the optimal solution contains the item n or not.
\begin{itemize}
\item \textbf{SELECT:} then it suffices to select items as \"much\" money from house 1-st to (n-2)th.
\item \textbf{ABANDON:} other, robber should select items as \"much\" money from house 1-st to (n-1)th.
\end{itemize}
\item Summarizing both two cases, the general form of sub-problem is: rob as \"much\" as money from house 1-st to i-th without two neighboring house. Denote the optimal solution as $OPT(i)$,and the money for $OPT(i)$ is $money(i)$.
\item Optimal sub-structure property:\\
\indent $OPT(n)=\max{\{OPT(n-1),OPT(n-2)+L(n)\}}$
\end{itemize}
\subsubsection{pseudo-code}

\SetKwFunction{FMaxMoney}{MaxMoney}
\SetKwProg{Fn}{Function}{}{}
%\begin{algorithm}
  \Fn{\FMaxMoney{$n$}}
  {
    \KwData{L: globle data, money for each house}
    \KwResult{T: globle data, houses that should be broken}
    \Begin{
      \If{$n = 0$}
      {
        \Return $0$\;
      }
      \uElseIf{$n = 1$}
      {
        \Return $L[n]$\;
      }
      \Else
      {
        $Selected=MaxMoney(n-2)+L[n]$\;\\
        $Abandon=MaxMoney(n-1)$\;\\
        \If{$Selected\ge Abonden$}
        {
          $T.pushback(L[n])$\;\\
          \Return $Selected$\;
        }
        \Else
        {
          \Return $Abandon$\;
        }
      }
    }
    $T$ is the solution\;
  }
%\end{algorithm}

\subsubsection{Correction}
 here we use mathematical induction to give a proof.
\begin{itemize}
\item when $i=0$, $OPT(0)=0$.
\item when $i=1$, $OPT(1)=L[1]$.
\item suppose we obtain the optimal value $OPT(k-1)$ and $OPT(k-2)$ .
\item when $i=k$,
\begin{itemize}
\item if $(k-1)^{th}$ house has been robbed, $k^{th}$ house should not be robbed, $OPT(k)=OPT(k-1)$.
\item if $(k-1)^{th}$ house has not been robbed, $(k-2)^{th}$ house should not be robbed, then $OPT(k-1)=OPT(k-2)$, $OPT(k)=OPT(k-1)+L[k]=OPT(k-2)+L[k]$.
\end{itemize}
\end{itemize}

\subsubsection{Time complexity}
$T(n)=O(n)$.

\subsection{the houses are in circle}
\subsubsection{optimal substructure}
When the houses are in circle, the robber cannot rob the first house and the last house one night.
\begin{itemize}
\item suppose we have got the optimal solution.
\item Consider the decision, whether the optimal solution contains the first house or not. if contains, then the robber should rob from first house to $(n-1)^{th}$ house. Otherwise, robber should rob from second house to $n^{th}$ house.
denote $OPT(i,j)$ as orignal problem: the optimal solution for $L[i]$ to $L[j]$, $OPT_{circle}(n)$ as the optimal solution of the problem for houses in circle.then
$OPT_{circle}(n)=\max{\{OPT(1.n-1),OPT(2,n)\}}$.
\end{itemize}

\subsubsection{pseudo-code}
\Fn{\FMaxMoneyInCircle{$n$}}
{
  \KwData{L: globle data, money for each house}
  \KwResult{T: globle data, houses that should be broken}
  \Begin{
    \Return $\max{\{ MaxMoney(1,n-1), MaxMoney(2,n) \}} $;\;
  }
}

\subsubsection{Time complexity}
$T(n)=O(n)$.

\section{Partition}
Given a string $s$, partition $s$ such that every substring of the partition is palindrome. Return the minimum cuts needed for a palindrome partitioning of $s$.

For example, given $s=\"aab\"$, return 1 since the pallindrome partition ["aa","b"]  could be produced using 1 cut.

\textbf{Solution:}
\begin{itemize}
\item Suppose we have got the optimal solution.
\item consider the first decision. i.e. how to deal with $n^{th}$ character. We denote $C_n={c1,c2...ck}$ as the cutting position list for $s[1]-s[n]$. then $OPT(n)=size(C_n)$. $s(i,j)$ as the substring of $s$ from $s[i]$ to $s[j]$.
\begin{itemize}
  \item case 1: $s(C_{n-1}[end]-1,n)$ is palindrome,like this(it can make the last substring as long as possible)\\\
  "aa|bab|cdc" + "b " $\to$ "aa|b|a|bcdcb"\\
  $temp=C_{n-1}.top();$\\
  $C_{n-1}.pop();$\\
  $temp1=C_{n-1}.top();$\\
  $C_{n-1}.pushback(temp1+1);$
  $C_n\leftarrow C_{n-1}.pushback(temp-1);$\\
  \item case 2: $s(C_{n-1}[end],n)$ is palindrome,like this\\
  " aa|b|cdc" + "b " $\to$ "aa|bcdcb"\\
  $C_n\leftarrow C_{n-1}$
\item case 3: otherwise,like this\\
" aa|b|cdc" + "a " $\to$ "aa|b|cdc|a"\\
$C_n\leftarrow C_{n-1}.pushback(n-1)$
\item Summarizing these three cases, the general form of sub-problem is: get the minimum cut for $s(1,i)$. Denote $C_i$ as the cutting position list for the optimal solution of $s(1,i)$.$OPT(i)=size(C_i)$ as the minimum cuts.
\item Optimal sub-structure property
\begin{equation*}
C_k= \left\{
\begin{array}{ll}
  0 & k=1\\
  process\ as\ above\\
\end{array}
\end{equation*}
\end{itemize}
\end{itemize}
\subsection{pseudo-code}
\SetKwFunction{FPartition}{Partition}
\Fn{\FPartition{}}
{
  \KwData{$s$: globle data, string for search}
  \KwResult{$C_n$: globle data,a list for cutting position, its size is the minimum cuts }
  \Begin{
  $n=size(s)$;\\
  \For{$i=1:n$}
  {
    \If{$i = 1$}
    {
      $C_1=NULL$\;
      \Continue;
    }
      \If{$s(C_{i-1}[end]-1,i)$ is palindrome}
      {
        $temp=C_{i-1}.top();$\\
        $C_{i-1}.pop();$\\
        $temp1=C_{i-1}.top();$\\
        $C_{i-1}.pushback(temp1+1);$
        $C_i\leftarrow C_{i-1}.pushback(temp-1);$\\
      }
      \uElseIf{ $s(C_{n-1}[end],n)$ is palindrome}
      {
        $C_i\leftarrow C_{i-1}$.
      }
      \Else
      {
        $C_i\leftarrow C_{i-1}.pushback(i-1)$
      }
    }
  }
  \Return $size(C_n)$;
}
\subsection{Correction}
这里的正确性主要体现在递推过程中列举的完善性，$s[i]$要想构成回文子串，将只和$s[i]$前一个回文子串有关，最远到达前一个子串的前一个元素。可以用反证法证明这个结论。
\subsection{Time Complexity}
假如判断一个字符串是不是回文需要$O(n)$的时间的话，该算法需要$O(n^2)$的时间。\\
我们可以通过一个表来记录每一次的判断，可以将每一次回文的判断降至$O(1)$，则总的时间复杂度为$O(n)$.\\
$T(n)=O(n)$.

\newpage
\section{Maximum Length}
Given a sequence of $n$ real numbers $a_1,a_2,...a_n$, determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.
\textbf{问题分析：}\\
该题的难点在于定义子问题的形式。指定$S$为输入的实数序列。
\begin{itemize}
  \item 设定子问题为$OPT(k)$，表示前$k$个数的最大递增序列的长度。
\begin{itemize}
  \item 我们在已知$OPT(n-1)=m$的情况下求$OPT$，不会求，情况太复杂。
  \item 我们在已知$OPT(n-1)=m$的情况下，还记录了这个递增序列$L_{n-1}={l_1,l_2...l_m}$，这时候有点头绪了，假如$S[n]>l_m$，则$L_n\leftarrow L_{n-1}+S[n]$，否则，不知道怎么处理……
  \item 我们记录所有的$L_k,\ k=1,2,..n-1$，似乎还是没法做……因为前面的最优解可能陷入一个单一序列。
\end{itemize}
\end{itemize}
通过上面的分析可知，最常用的子问题形式可能不可行，这里分析该问题的解的性质：在计算出所有可能是最优解的序列之前，我们无法判断哪个是最优解，而且，由于是递增序列，所以中间序列的最大值是非常关键的信息，所以我们可以考虑按照中间序列的最大值来对问题进行分解。\\
\begin{itemize}
  \item 假设$C[k]$记录以$S[k]$为最大值的递增序列的长度，则$OPT(k)=\max{\{C[1],C[2],...C[k]\}}$。
\begin{itemize}
  \item 已知$C[1],C[2]...C[k-1]$，则$C[k]=\max{\{C[j]\}},j<k \&\& S[j]<S[k]$.
\end{itemize}
\end{itemize}
代码及测试如下：
\lstset{language=Matlab}%代码语言使用的是matlab
\lstset{breaklines}%自动将长的代码行换行排版
\lstset{extendedchars=false}%解决代码跨页时，章节标题，页眉等汉字不显示的问题
\begin{lstlisting}[frame=single]
function max_num=MaxAscendingLength(S);
%MaxAscendingLength: get the size of the longest strictly increasing
%sequence of a list.
%max_num=MaxAscendingLength(S):S is a real number list, max_num is the the size of the longest strictly increasing
%sequence of S.
S=reshape(S,[],1);
S_size=size(S);
len=S_size(1);
C=ones(len,1);
for j=2:len
    for k=1:j-1
        if S(k)<S(j)
            C(j)=max([C(j),C(k)+1]);
        end
    end
end

max_num = max(C);
end
\end{lstlisting}
测试代码如下：
\begin{lstlisting}
>> S=[1;2;3;5;4];

>> MaxAscendingLength(S)

ans =

     4

>> S=[1;11;21;2;12;22;32;3;13;23;33;43;4;14;24;34;5;15;25];
>> MaxAscendingLength(S)

ans =

     7

\end{lstlisting}


\end{document}
